package com.lisp.algorithm.test.sort;

import java.util.Arrays;
import java.util.Random;

import com.lisp.algorithm.util.Assert;

public class Heap {

	private int[] data;
	
	private int heapSize;
	
	public Heap(int[] data) {
		this.data = data;
		init();
	}

	public void sort() {
		for(int i=data.length-1; i>0; i--) {
			int tmp = data[i];
			data[i] = data[0];
			data[0] = tmp;
			normalize(0, i);
		}
	}
	
	public int max() {
		return data[0];
	}
	
	public int extractMax() {
		heapSize--;
		int ret = data[0];
		data[0] = data[heapSize];
		data[heapSize] = ret;
		normalize(0, heapSize);
		return ret;
	}
	
	public void increaseKey(int i, int newVal) {
		if(newVal <= data[i]) {
			throw new IllegalArgumentException("newVal must be bigger");
		}
		data[i] = newVal;
		while(i > 0 && newVal > data[parent(i)]) {
			data[i] = data[parent(i)];
			data[parent(i)] = newVal;
			i = parent(i);
		}
	}
	
	public void insert(int key) {
		if(heapSize == data.length) {
			int[] data2 = new int[data.length + 1];
			System.arraycopy(data, 0, data2, 0, data.length);
			data2[data.length] = Integer.MIN_VALUE;
			this.data = data2;
		} else {
			data[heapSize] = Integer.MIN_VALUE;
		}
		
		increaseKey(heapSize, key);
		heapSize++;
	}
	
	private int parent(int i) {
		return (i-1)/2;
	}

	private void normalize(int i, int endIndexExclusive) {
		int largestIndex = i;
		
		int left = left(i);
		if(left < endIndexExclusive && data[left] > data[i]) {
			largestIndex = left;
		}
		
		int right = left + 1;
		if(right < endIndexExclusive && data[largestIndex] < data[right]) {
			largestIndex = right;
		}
		
		if(largestIndex != i) {
			int tmp = data[i];
			data[i] = data[largestIndex];
			data[largestIndex] = tmp;
			normalize(largestIndex, endIndexExclusive);
		}
	}
	
	private void init() {
		this.heapSize = data.length;
		for(int i = data.length / 2 - 1; i>=0; i--) {
			normalize(i, heapSize);
		}
	}
	
	private int left(int i) {
		return (i << 1) + 1;
	}

	public int[] getData() {
		return data;
	}

	public void setData(int[] data) {
		this.data = data;
	}
	
	
	public void verify() {
		for(int i=0; i<heapSize/2; i++) {
			int left = left(i);
			Assert.isTrue(data[i] >= data[left]);
			
			int right = left + 1;
			if(right < heapSize) {				
				Assert.isTrue(data[i] >= data[right]);
			}
		}
	}
	
	public static void main(String[] args) {
		int data[] = {20, 8, 5, 30, 48, 9, 11, 1, 100};
		Heap heap = new Heap(data);
		System.out.println(Arrays.toString(heap.getData()));
		heap.verify();
		
		System.out.println("---------extraceMax----------");
		for(int i=0; i<3; i++) {			
			System.out.println(heap.extractMax());
			System.out.println(Arrays.toString(heap.getData()));
			heap.verify();
		}
		
		Random random = new Random();
		for(int i=0; i<4; i++) {
			int nextInt = random.nextInt(120);
			System.out.println("---------insert----------" + nextInt);
			heap.insert(nextInt);
			System.out.println(Arrays.toString(heap.getData()));
			heap.verify();
		}
		
		System.out.println("---------increaseKey----------");
		for(int i=5; i<9; i++) {
			heap.increaseKey(5, heap.getData()[5] + 10);
			System.out.println(Arrays.toString(heap.getData()));
			heap.verify();
		}
	}
}
